// 1. 爬楼梯
function climbStairs(n) {
    let dp = []
    dp[0] = 0, dp[1] = 1, dp[2] = 2
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i-2] + dp[i-1]
    }
    return dp[n]
}
// console.log(climbStairs(5))  // 8

// 2. 打家劫舍
let robTo = function(nums, lastIndex) {
    if (lastIndex === 0) return nums[0]
    if (lastIndex === 1) return nums[1]
    let sum1 = robTo(nums, lastIndex - 2) + nums[lastIndex]
    let sum2 = robTo(nums, lastIndex - 1)
    return Math.max(sum1, sum2)
}
let rob = function(nums) {
    return robTo(nums, nums.length - 1)
}
// console.log(rob([1,3,2,4,5,3,2]));   // 10

// 3. 最大正方形
let maximalSquare = function(matrix) {
    if (matrix.length === 0 || matrix[0].length === 0) return 0
    let maxSide = 0, rows = matrix.length, columns = matrix[0].length
    let dp = new Array(rows).fill(0).map(() => new Array(columns).fill(0))
    for(let i = 0; i < rows; i++) {
        for(let  j = 0; j < columns; j++) {
            if(matrix[i][j] == '0') continue
            dp[i][j] = Math.min(
                dp[i-1]?.[j] || 0,
                dp[i][j-1] || 0,
                dp[i-1]?.[j-1] || 0
            ) + 1
            maxSide = Math.max(maxSide, dp[i][j])
        }
    }

    return maxSide*maxSide
}

// 4. 零钱兑换
const coinChange = (coins, amount) => {
    let dp = new Array(amount + 1).fill(Infinity)
    dp[0] = 0
    for(let i = 0; i < coins.length; i++) {
        for(let j = coins[i]; j <= amount; j++) {
            dp[j] = Math.min(dp[j-coins[i]] + 1, dp[j])
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount]
}
console.log(coinChange([1,2,5],11));

// 5. 斐波那契数列
function fibonacci(n) {
    if (n <= 2) return 1
    return fibonacci(n-2) + fibonacci(n-1)
}

// 6. 不同路径
function uniquePaths(m, n) {
    const f = new Array(m).fill(0).map(() => new Array(n).fill(0))
    for(let i = 0; i < m; i++) {
        f[i][0] = 1
    }
    for(let j = 0; j < n; j++) {
        f[0][j] = 1
    }
    for(let i = 1; i < m; i++) {
        for(let j = 1; j < n; j++) {
            f[i][j] = f[i-1][j] + f[i][j-1]
        }
    }
    return f[m-1][n-1]
}

// 7. 最长公共子序列
function LCS(s1, s2) {
    // 状态：f[i][j]表示以text1第i个结尾text2第j个结尾的的公共子串；
    // 状态转移方程: 当text1[i] === text2[j]时：f[i][j] = f[i-1][j-1] + text[i];
    //             当text1[i] !=== text2[j]时；f[i][j] = max{dp[i-1][j], dp[i][j-1]};
    const l1 = s1.length, l2 = s2.length
    const dp = new Array(l1).fill(0).map(() => new Array(l2).fill(''))
    let max = ''
    for(let i = 0; i < l1; i++) {
        for(let j = 0; j < l2; j++) {
            if(s1[i] === s2[j]) {
                dp[i][j] = (i === 0 || j === 0) ? s1[i] : dp[i-1][j-1] + s1[i]
            } else {
                const tempS1 = i === 0 ? '' : dp[i-1][j]
                const tempS2 = j === 0 ? '' : dp[i][j-1]
                if(i === 1) tempS1
                dp[i][j] = tempS1.length > tempS2.length ? tempS1 : tempS2
            }
            max = dp[i][j].length > max.length ? dp[i][j] : max
        }
    }
    // console.log(dp);
    return max.length ? max : -1
}
// console.log(LCS('1a2b3e','b1d23ae'));

//8. 最长公共子串
function LCS2( str1 ,  str2 ) {
    let dp = new Array(str1.length+1).fill(0).map(() => new Array(str2.length+1).fill(0));
    let max = 0;
    const map = new Map()
    for(let i = 1;i<=str1.length;i++){
        for(let j = 1;j<=str2.length;j++){
            if(str1[i-1] === str2[j-1]){
                dp[i][j] = dp[i - 1][j - 1] + 1
                max = Math.max(max,dp[i][j])
                if(!map.has(max)) map.set(max,i)  //避免重复
            }
        }
    }
    let startIndex = map.get(max) - max;
    let endIndex = map.get(max) ;
    return str1.substring(startIndex,endIndex)  //截取字符串
}

// 贪心
// 9.剪绳子
// 贪心的话尽可能把分成长度为3的小段，这样乘积最大
function cuttingRope(n) {
    if(n < 4) return n - 1
    let res = 1
    while(n > 4) {
        res *= 3
        n -= 3
    }
    return res * n
}
// 动态规划
function cuttingRope2(n) {
    let dp = new Array(n + 1).fill(0)
    dp[2] = 1
    //如果只剪掉长度为1，对最后结果无增益，所以长度为2开始剪
    for(let i = 2; i <= n; i++) {
        for(let j = 1; j < i; j++) {
            //剪了第一段后，剩下i-j长度可以剪或不剪；不剪长度乘积为j*(i-j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值
            let bigger = Math.max(j * (i-j), j * dp[i-j])
            //对于同一个i，内层循环对不同的j都还会拿到一个max，所以每次内循环都要更新max
            dp[i] = Math.max(dp[i], bigger)
        }
    }
    return dp[n]
}

//10. 跳跃游戏
function canJump(nums) {
    let n = nums.length, rightMost = 0;
    for(let i = 0; i < n; i++) {
        // 如果i比rightMost大说明中间有位置到不了了
        if(i <= rightMost) {
            // 可以到达的位置
            rightMost = Math.max(rightMost, i + nums[i])
            if(rightMost >= n-1) {
                return true
            }
        }
    }
    return false
}
// console.log(canJump([3,2,1,0,4]));

// 11.加油站
function canCompleteCircuit(gas, cost) {
    let totalGas = 0, totalCost = 0;
    for(let i = 0; i < gas.length; i++) {
        totalGas += gas[i]
        totalCost += cost[i]
    }
    if(totalCost > totalGas) return -1

    let currentGas = 0, start = 0;
    for(let i = 0; i < gas.length; i++) {
        currentGas = currentGas - cost[i] + gas[i]
        //如果到达下一站的时候油量为负数,就以这个站为起点重新计算
        if(currentGas < 0) {
            currentGas = 0
            start = i + 1
        }
    }
    return start
}

//二分
//12.二分查找
function search(nums, target) {
    let l = 0, r = nums.length - 1
    while(l <= r) {
        let mid = Math.floor(l + (r-l)/2)
        if(nums[mid] === target) return mid
        else if(nums[mid] > target) r = mid - 1
        else {
            l = mid + 1
        }
    }
    return -1
}

//13.第一个错误的版本
function solution(isBadVersion) {
    return function(n) {
        let left = 1, right = n
        while(left < n) {
            const mid = Math.floor(left + (right-left)/2)
            if(isBadVersion(mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}

//14.搜索插入位置
function searchInsert(nums, target) {
    let l = 0, r = nums.length - 1
    while(l <= r) {
        let mid = (l+r) >> 1
        if(target > nums[mid]) {
            l = mid+1
        } else {
            r = mid - 1
        }
    }
    return l
}

//15. 排序数组中两个数字之和
function twoSum(numbers, target) {
    // 从数组第一个元素开始，用二分查找判断后面的元素是否为target-numbers[i]
    for(let i = 0; i < numbers.length; i++) {
        const x = numbers[i]
        const index = binarySearch(numbers, i+1, numbers.length-1, target-x)
        if(index !== -1) {
            return [i, index]
        }
    }
    return []
}
function binarySearch(number, left, right, target) {
    while(left <= right) {
        const mid = left + Math.floor((right-left)/2)
        if(target === number[mid]) {
            return mid
        }else if(target < number[mid]) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

//16.山峰数组的顶部
function peakIndexInMountainArray(arr) {
    let l = 0, r = arr.length - 1, target = Math.max(...arr)
    while(l <= r) {
        const mid = l + Math.floor((r-l)/2)
        if(arr[mid] === target) return mid
        if(arr[mid] < arr[mid+1]) {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return -1
}
function guess(mid){
    return mid
}
//17.猜数字大小
function guessNumber(n) {
    let l = 1, r = n
    while(l <= r) {
        let mid = Math.floor((l+r)/2)
        if(guess(mid) === 0) return mid
        else if(guess(mid) === 1) l = mid+1
        else { r = mid - 1 }
    }
}

//18.x的平方根
function mySqrt(x) {
    let l = 1, r = x;
    while(l <= r) {
        let mid = Math.floor((l+r) / 2)
        if(mid*mid === x) return mid
        if(mid*mid > x) {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return l - 1
}

//19.旋转数组的最小数字
function minArray(numbers) {
    let l = 0, r = numbers.length - 1
    while(l < r) {
        let mid = Math.floor((l+r) / 2)
        if(numbers[mid] === numbers[r]) {
            // 有可能有重复数字
            r--
        } else if(numbers[mid] < numbers[r]) {
            // mid有可能是最小值
            r = mid
        } else {
            l = mid + 1
        }
    }
    return numbers[l]
}

//20. 数组中的逆序对
function reversePairs(nums) {
    let count = 0
    // 如果数组中只有一个元素或者为空，则不存在逆序对
    if(nums.length < 2) return count
    const mergeSort = (front, behind) => {
        // 如果前后指针相遇，则归并区间只剩下一个元素
        if(front === behind) return [nums[front]]
        let mid = front + ((behind - front) >> 1)
        // 规则让左半部分不包含中心元素，右半部分包含中心元素
        let left = mergeSort(front, mid)
        let right = mergeSort(mid+1, behind)
        let temp = new Array(behind - front + 1).fill(0)
        // 合并三个指针
        let cur = 0, l = 0, r = 0
        while(l < left.length && r < right.length) {
            // 如果右边元素大于左边元素，将左边元素放到结果数组中
            if(right[r] >= left[l]) temp[cur++] = left[l++]
            else {
                temp[cur++] = right[r++]
                // 如果左边元素大于右边元素，那就出现了序列对了
                // 由于左右两边都是有序的，左边当前元素及之后的元素都会跟右边构建逆序对
                count += left.length - l;
            }
        }
        while (l < left.length) temp[cur++] = left[l++];
        while (r < right.length) temp[cur++] = right[r++];
        return temp;
    }
    // 左闭右闭区间
    mergeSort(0, nums.length - 1);
    return count;
}